﻿#define parent(left,i) left[(i)/2]
#define lchild(left, i) left[2*(i)+1]
#define rchild(left, i) left[2*(i)+2]
inline void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
void buildHeap(int *left, int n);
void upAdjust(int *left, int i);
void downAdjust(int *left, int n, int i);
//最大堆排序
void heapSort(int *left, int n)
{
    buildHeap(left, n);
    while(n > 1) {
        swap(left[0], left[n-1]);
        --n;
        downAdjust(left,n,0);
    }
}
void buildHeap(int *left, int n)
{
    int i = n - 2;
    if ( n % 2 == 0) {
        i = n - 1;
        if (left[i] > parent(left,i)) {
            swap(left[i], parent(left,i));
        }
        i -= 2;
    }
    for (; i > 0; i -= 2) {
        if (left[i] > parent(left,i)) {
            if (left[i] > left[i + 1]) {
                swap(left[i], parent(left,i));
                downAdjust(left,n, i);
            } else {
                swap(left[i + 1], parent(left,i));
                downAdjust(left,n, i + 1);
            }
        } else if(left[i + 1] > parent(left, i)){
            swap(left[i + 1], parent(left,i));
            downAdjust(left,n, i + 1);
        }
    }
}
void upAdjust(int *left, int i)
{
    while (0 < i && parent(left,i) < left[i]) {
        swap(parent(left,i), left[i]);
        i /= 2;
    }
}
void downAdjust(int *left, int n, int i)
{
    while ( i < n / 2) {
        if (2 * i + 2 == n) {
            if (lchild(left,i) > left[i])
                swap(lchild(left,i), left[i]);
            break;
        }
        if ( left[i] > lchild(left,i) && left[i] > rchild(left,i))
            break;
        else if (rchild(left,i) < lchild(left,i)) {
            swap(left[i], lchild(left,i));
            i = i * 2 + 1;
        } else {
            swap(left[i], rchild(left,i));
            i = i * 2 + 2;
        }
    }
}

